/* cutpoints search */
namespace cutpoints
{
	vector <int> seek_cutpoints(vector <vector <int> > &g);
	void dfs(vector <vector <int> > &g, int point, int par = -1);
	vector <int> result, tin, fup;
	int tick = 0;
	vector <bool> used;
}

vector <int> cutpoints::seek_cutpoints(vector <vector <int> > &g)
{
	tick = 0;
	result.clear();
	tin.resize(g.size(), 0);
	fup.resize(g.size(), 0);
	used.resize(g.size(), false);
	
	dfs(g, 0);
	sort(allx(result));
	result.resize(unique(allx(result)) - result.begin());

	// cleanup
	tin.clear(); fup.clear(); used.clear();
	
	return result;
}

void cutpoints::dfs(vector <vector <int> > &g, int point, int par)
/*
	fup[point] is the t_in time of the vertex, which can be reached from [point]'s subtree
		and has minimal of t_in time from all of these vertexes. 
*/
{
	used[point] = true;
	tin[point] = fup[point] = tick, tick++;

	// count of children, for root's exception case
	int chl = 0;
	
	forx(i, g[point].size())
	{
		int c = g[point][i];

		if (c == par)
			// trying to visit parental vertex
			continue;
		
		if (used[c])
			// trying to go through back edge
			fup[point] = min(fup[point], tin[c]);
		else
		{
			// travel down
			dfs(g, c, point);

			// recalculating fup[point], USING fup[c]
			fup[point] = min(fup[point], fup[c]);

			if (fup[c] >= tin[point] && par != -1)
				// cutpoint found
				result.push_back(point);
			chl++;
		}
	}

	// handling root's exceptional case
	if (par == -1)
		if (chl > 1)
			result.push_back(point);
}